Functions that can modify objects in the environment
Other functions
7. Partial computations
8. Substitution of indeterminates
9. Expressions
----------------------------------------------
1. Menus
Apple Menu, File Menu, Edit Menu.
They are the standard menus which allow typical Macintosh operations: opening desk accessories, opening, saving and printing files and doing basic editing actions.
Keyboard menu.
This menu allows the user to switch between the Italian keyboard and the UK keyboard. This makes easier to locate the keys corresponding to special characters (exponents, indexes, etc.).
Ring menu.
At any time a ΓÇÿcurrent ringΓÇÖ is active within the system; this ring is the polynomial ring within which the evaluations are done. The current ring setting can be examined and changed at any time by simply pulling down the menu ΓÇÿRingΓÇÖ and selecting the item ΓÇÿSet RingΓÇÖ. Then a dialog box appears (called ΓÇÿRing SettingΓÇÖ); this dialog shows how the current ring is set and enables the user to change the setting. Its content will be discussed in more detail in the next section.
2. The Ring
The current ring is completely determined by:
- the name (and hence also the number) of the indeterminates;
- their weights;
- the field of the coefficients;
- the term ordering.
indeterminates
The maximum number of indetermianates that the system can manage is 23. An indeterminate is represented by a name consisting of either
- a single letter (a character in the set {a, ..., z, A, ..., Z}) or
- a letter followed by an index having up to eleven digits.
Corresponding upper and lower case letter yield different indeterminates.
For example, x, X and and x123 are legal (and different) indeterminates; they are set by entering the string ΓÇ£xXx123ΓÇ¥ in the ΓÇ£Set RingΓÇ¥ dialog (no spaces!).
weights
Each indeterminate has a weight (a positive integer). The system defaults to the value of 1 for all the indeterminates. If the weights specified in the dialog box are less than the indeterminates, then the missing ones – the last ones – are assumed to be equal to 1 (the system notifies the user that it is making this assumption).
coefficients
The coefficients can be either rational numbers or integers modulo p.
This is done by setting the characteristic either to 0 or to p (p < 32767). When the dialog box is closed pushing the OK button, the system checks whether p is a prime number and, if it is not, then a message is given. However all non negative integers are accepted, so it is possible to do some work with polynomials whose coefficients are not in a field but it is up to the user to ensure that no illegal operation will be attempted. The system simply reports an error message every time the inversion of a zeroΓÇôdivisor is attempted, but does not interrupt a computation; beware hence of computing Gr├╢bner bases in presence of zeroΓÇôdivisors, since it is very likely that you end up with avery long sequence of error messages.
objects
The system can handle objects of the following kind:
- polynomials;
- lists of polynomials;
- matrices of polynomials;
- ideals;
- modules (submodules of a free module).
Each object may have a ΓÇÿnameΓÇÖ. Names of objects have the same structure of names of variables, i.e. they can be a single letter or a letter followed by an index (but, of course, an object cannot have the same name of a variable of the current ring).
orderings
The polynomials are always kept sorted with respect to the given term ordering. All the operations involving polynomials preserve and benefit of this ordering. In the current release the user can choose among three predefined term orderings or define custom orderings. The predefined term orderings are the following:
- the ΓÇÿdegree reverse lexicographicΓÇÖ (which is the default one),
- the ΓÇÿdegree lexicographicΓÇÖ,
- the ΓÇÿpure lexicographicΓÇÖ.
Selection of one of these orderings is achieved by just pushing the corresponding button in the dialog box. The first two term orderings use the weights appearing in the dialog box to calculate the degree. For computations requiring temporarily a different term ordering (for example, in the case of the elimination of variables from an ideal), the system changes automatically the term ordering to a more suitable one, performs the computation, and then restores the initial term ordering and gives its output with respect to this one; in this way the user never has to deal with temporary changes.
For special purposes, the user can also enter directly a matrix corresponding to a custom ordering by pushing the putton ΓÇÿOtherΓÇÖ. A new dialog is opened where the current ordering is displayed. The user can freely modify this ordering; the system does not check whether this is a term ordering, so be careful. Note: The ordering becomes effective only upon exit from the ΓÇÿRing settingΓÇÖ dialog, and so it applies to the number of indeterminates at that moment. So if the user enters a 4x4 matrix, changes the number of indeerminates to 5 and then exits, an error message will be displayed.
Each term ordering on the current ring induces several term ordering on free modules. The system allows to choose between two of them by pushing the button ΓÇÿModules optionsΓÇÖ in the ring dialog box. If M is a free module of rank r over the ring R and {e(i): i=1,...,r} is the canonical basis, then a term of M is an element of the form Te(i) where T is a term of R. The possible choises to compare two terms of a module are:
- the ordering called ΓÇÿTO-PosΓÇÖ (which is the default one)
TΓüäe(i) > TΓé¼e(j) iff TΓüä > TΓé¼ in R or, if TΓüä = TΓé¼ , i < j
- the ordering called ΓÇÿPos-TOΓÇÖ
TΓüäe(i) > TΓé¼e(j) iff i < j or, if i = j, TΓüä > TΓé¼ in R .
By pushing the button ΓÇÿGbasis optionsΓÇÖ in the ring dialog box, another dialog box appears; this dialog allows the advanced user to change the values of some special parameters which affect the way in which the computation of a Gr├╢bner basis is carried out. These parameters are discussed in some detail in Appendix A of Cocoa Users' Manual.
Finally the button ΓÇÿOther OptionsΓÇÖ and the corresponding dialog box allow to set some parameters which affect the way in which numerical polynomials are written and to choose the variable for Poincare series. More details are given in Appendix B of Cocoa Users' Manual.
3. Executing commands
key ΓÇÿEnterΓÇÖ
To notify the system that some action has to be performed on some data, the user has to press the key ΓÇÿEnterΓÇÖ; at this point a part of the text of the window is taken as being the ΓÇÿcurrent commandΓÇÖ:
- if there is no selection point (the cursor is blinking somewhere) then the part of text between the beginning of the line where the cursor is placed and the cursor itself is taken as current command;
- if there is a nonnull selection range, then the whole selection is taken as current command (in this way the system can process multiline commands).
A command may consist of a single instruction or of a sequence of instructions separated by semicolons. In this latter case the instructions are executed in sequence if some error occurs, then the instructions subsequent to the error are not executed.
instructions
Each instruction can be:
- an expression (including the case of a simple identifier): in this case the expression is evaluated and the result is displayed starting at the line after the cursor;
examples:
(x+y)™; j; det(M) + G mod F ; (I&J)™ ; Gbasis(x£-y,x¢-z)
- an assignment (a command of the form ΓÇÿidentifier = expressionΓÇÖ): in this case the expression is first evaluated and then the resulting value is assigned to the identifier; the computed value is not displayed; this is the way of giving a name to an object. The new value overrids any value previosly associated to that name, which is lost.
examples:
F = (xy+zt)∞ ; G = F[x=3y™-t∞] ; J = ideal(F, x+y, G™+xz):I™ ; M = syz(J)€fi
- a procedure call (possibly with a parameters list): the behaviour of the system in this case strictly depends on the procedure called;
examples:
List; Cancel(F,J,M); Gbasis(I); Write(I.Gbasis)
Named objects (i.e., objects which have been associated to a name by the execution of assignments) are stored in an environment. The name of an object may be used in expressions at every place where an object of that kind can occur. The list of the identifiers present in the environment together with their type can be obtained by executing the command ΓÇÿListΓÇÖ.
Expressions follow a simple syntax which is very close to the usual mathematical one (its definition by means of syntax graphs can be found in Appendix C of Cocoa Users' Manual, but for most uses the ΓÇÿintuitionΓÇÖ will suffice).
4. About identifiers and special characters
There are two kinds of identifier:
- the identifier of a indeterminate or of an object;
- the identifier of a procedure or of a function built in the system.
The identifiers of the first kind must be made of either a single letter or of a letter followed by an index having at most 11 digits. Different identifiers do always correspond to different objects, and identifiers are case sensitive (corresponding upper and lower case letters yield different identifiers). If to a name which is already associated with an object is assigned another object, then the new association overrids the old one.
The identifier of a procedure or a function consists of a contiguous sequence of letters. The corresponding upper- and lower-case letters in the word are equivalent, so, for example, LIST, list, List are all accepted and they all call the same procedure. If the procedure or function has some parameters, then these are enclosed within round brackets and usually separated by commas.
The system uses its own font containing special characters and makes provision for using both the italian keyboard and the UK keyboard. The italian keyboard is assumed by default. If the UK keyboard is used, then the user has to select ΓÇÿUK keyboardΓÇÖ from the Keyboard menu. We give here a table showing how to enter special characters:
The following procedures are not related to the part of the system devoted to algebraic computations, but only to the system management itself.
Cancel(iΓüä,iΓé¼,...)
This procedure deletes the objects associated to the identifiers iΓüä, iΓé¼,... from the environment.
Help
This procedure invokes this online help.
Info
This procedure displays information related to memory usage and garbage collection; it is of interest only to the system developers.
List
This procedure displays the list of the identifiers of the objects present in the environment together with their type (not their value);
Timeron
This procedure enables the displaying of the time that each instructions take to execute; after its execution, the execution of subsequent commands will be followed by their execution time;
Timeroff
This procedure disables the displaying of the execution time.
Write(i) or Write(i . ext)
This procedure displays the object stored in the environment with identifier i or, in the second form, the part of the ideal or module specified by ΓÇÿextΓÇÖ; more precisely the system will display only
- the generators of i if ext = Gens;
- the gbasis of i if ext = Gbasis;
- the standard basis of i if ext = Stbasis; (only for ideals)
- the Poincaré series of i if ext = Poincare; (only for ideals)
6. Algebraic procedures and functions
We give in this section the list of the functions available in the system, together with the pattern with which they can be called; some functions can also be called like procedures, in which case after the call the resulting value will usually be displayed on the screen. For each of the patterns the type of the parameters and of the object returned or displayed are described.
-- Functions returning a polynomial --
Der(F, x) where F : polynomial; x: indeterminate;
It returns the derivative of the polynomial F w.r.t. the indeterminate x.
Det(M) where M : matrix;
It returns the determinant of the square matrix M .
Gcd(FΓüä, FΓé¼,...) where FΓüä, FΓé¼,... : polynomials;
It returns the greatest common divisor of the polynomials FΓüä, FΓé¼,... .
Homog(x, F) where x : indeterminate; F : polynomial;
It returns the polynomial which is the homogeneization of the polynomial F w.r.t. the indeterminate x and current weights of the indeterminates.
Lcm(FΓüä, FΓé¼,...) where FΓüä, FΓé¼,...: polynomials;
It returns the least common multiple of the polynomials FΓüä, FΓé¼,... .
NormalForm(F, I) where F : polynomial; I : ideal;
It returns the polynomial which is the normal form of the polynomial F w.r.t. the ideal I . If I is an ideal stored in the environment and a Gbasis of I has already been computed, then that Gbasis is used otherwise the Gbasis of I w.r.t. the current term ordering is computed.
Resultant(F, G, x) where F, G : polynomials; x : indeterminate;
It returns the resultant of the polynomials F and G w.r.t. the indeterminate x and also displays the Sylvester matrix.
-- Functions returning a list of polynomials --
First we note that the value of the expression
{FΓüä, FΓé¼,...} where FΓüä, FΓé¼,... : polynomials
is the list of the polynomials FΓüä, FΓé¼,... and it may be assigned to an identifier.
GBasis(FΓüä, FΓé¼,...) where FΓüä, FΓé¼,... : polynomials;
GBasis(L) where L : list of polynomials;
They return a list of polynomials which is a Gr├╢bner basis of the ideal generated by FΓüä, FΓé¼,... or by the list L . The result depends on the current term ordering and on the setting of the parameters in the window ΓÇ£GBasis optionsΓÇ¥. The default setting produces the fully interreduced Gr├╢bner basis with monic polynomials , which is unique.
Gens(I) where I : ideal;
It returns the list of polynomials than generate the ideal I .
Homog(x, FΓüä, FΓé¼,...) where x : indeterminate; FΓüä, FΓé¼,...: polynomials;
Homog(x, L) where x : indeterminate; L : list of polynomials;
These two functions return the list of polynomials whose members are the homogeneizated of the polynomials FΓüä, FΓé¼,... or of polynomials in L w.r.t. the indeterminate x.
InterReduce(FΓüä, FΓé¼,...) where FΓüä, FΓé¼,...: polynomials;
InterReduce(L) where L : list of polynomials;
These two functions return the list of polynomials obtained from the polynomials FΓüä, FΓé¼,... or from the members of L by interreducing them. Note that, in general, the result depends on the current term ordering.
LeadTerm(FΓüä, FΓé¼,...) where FΓüä, FΓé¼,...: polynomials;
LeadTerm(L) where L : list of polynomials;
They return the list of the leading terms of the polynomials FΓüä, FΓé¼,... or of the members of L .
StBasis(FΓüä, FΓé¼,...) where FΓüä, FΓé¼,...: polynomials;
StBasis(L) where L : list of polynomials;
They return a list of polynomials which is a standard basis of the ideal generated by FΓüä, FΓé¼,... or by L .
-- Functions returning an ideal --
Elim(x, I) where x : indeterminate; I : ideal;
This function returns the ideal obtained by eliminating the indeterminate x from the generators of the ideal I. A suitable term ordering is set during the computation and then the initial ordering is restored.
Elim(x..y, I) where x, y : indeterminates; I : ideal;
It returns the ideal obtained by eliminating the indeterminates included between x and y from the generators of the ideal I. (Note the two dots ΓÇÿ..ΓÇÖ as part of the syntax).
Homog(x, I) where x : indeterminate; I : ideal;
It returns the ideal which is the homogeneization of the ideal I w.r.t. the indeterminate x.
Ideal(FΓüä, FΓé¼,...) where FΓüä, FΓé¼,...: polynomials;
Ideal(L) where L : list of polynomials;
They return the ideal generated by the polynomials FΓüä, FΓé¼,... or by the list L.
InterReduce(I ) where I : ideal;
It returns the ideal obtained from I by interreducing the generators.
LeadTerm(I) where I : ideal;
It returns the ideal of the leading terms of the ideal I.
MaxMinors(M) where M : px(p+1) or px(p-1)-matrix;
It returns the ideal generated by the maximal minors of the matrix M .
-- Functions returning a module --
InterReduce(M) where M : module;
It returns the module obtained fromM by interreducing its generators.
LeadTerm(M) where M : module;
It returns the module generated by the leading term of the elements of the Gbasis of M w.r.t. the current term ordering.
Module(r, FΓüä, FΓé¼,..) where r : positive integer; FΓüä, FΓé¼,.. : polynomials;
It returns the submodule (of a free module of rank r) generated by the r-uples of polynomials in FΓüä, FΓé¼,... (separated by semicolons). If necessary an appropriate number of zero polynomials is added at the end of the list.
Example ( r=3 )
Module(3, F⁄, F€, F‹ ; F›, Ffi)
is the 3-rank module generated by (F⁄, F€, F‹) and (F›, Ffi, 0).
Syz(I) where I : ideal or a module;
It returns the module of syzygies of the generators of I.
It returns the r x s matrix whose entries are the polynomials FΓüä, FΓé¼,... If the polynomials are less than rs, then an appropriate number of null polynomials is added at the bottom of the list.
Transp(M) where M: matrix;
It returns the transposed of the matrix M.
-- Functions that can modify objects in the environment --
When the parameter in the following patterns is an object stored in the environment (more precisely it is the identifier of an object stored in the environment), then the function modify the object (usually it adds some data to the object) and, if it is called like a procedure, nothing will be displayed.
GBasis(I) where I : ideal or module;
It computes the reduced Gr├╢bner basis of the ideal I with respect to the current term ordering and returs the result as list of polynomials; if I is the identifier of an ideal or module, then the Gr├╢bner basis is also stored in the object I and not displayed, otherwise it is simply sent to the screen.
StBasis(I) where I : ideal or module;
It computes a standard basis of the ideal I and it behaves like GBasis.
Poincare(I) where I : ideal or module;
It computes and displays the Poincare series of the ideal of the leading terms of I (hence of I if I is homogeneous). If I is the identifier of an ideal or module, then the series is also stored in the object I .
-- Other functions --
Hilbert(I) where I : ideal or module;
It computes the Hilbert polynomial of the ideal of the leading terms of I (hence of I if I is homogeneous).
HilbertFn(I,n) where I : ideal or module;
It displays the n-th value of the Hilbert function of the ideal of the leading terms of I (hence of I if I is homogeneous).
HilbertFn(I) where I : ideal or module;
It displays the values of the Hilbert function up to the index of regularity and the Hilbert polynomial of the ideal of the leading terms of I
(hence of I if I is homogeneous).
Dim(I) where I : ideal or module;
It computes the dimension of the ideal of the leading terms of I (hence of I if I is homogeneous).
Mult(I) where I : ideal or module;
It computes the multiplicity of the ideal of the leading terms of I (hence of I if I is homogeneous).
Reg(I) where I : ideal or module;
It computes the index of regularity of the ideal of the leading terms of I (hence of I if I is homogeneous).
7. Partial computations
It is possible to compute only a part of a Gbasis or of a syzygy module: when the commands Gbasis(...) and Syz(...) are followed by an index N, then the computation is stopped as soon as an element of degree greater than N is found. If the ideal is homogeneous, then this gives the whole Gbasis (or syzygy module) up to degree N.
Example: if I is an homogeneous ideal, then
Gbasis(I)€fi
compute the Gbasis of I up to degree 25.
8. Substitution of indeterminates
It is possible to substitute indeterminates with polynomials within expressions. Let E be an expression denoting an object O and let xΓüä, xΓé¼, ... be indeterminates and let FΓüä, FΓé¼, ... be polynomials. Then
E [xΓüä= FΓüä, xΓé¼ = FΓé¼ , ... ]
is the object obtained from evaluating E to O and then by simultaneously substituting in O all the occurrences of the variables xΓüä, xΓé¼, ... with the polynomials FΓüä, FΓé¼, ....
Of course if O is an ideal or a module, then the substitution takes effect only on the generators and the resulting value is not associated with any Gr├╢bner basis and/or standard basis with which is possibly associated O.
Expressions have a rather natural sintax, quite similar to that of Pascal language. Expression are made of factors and terms. These objects are described in Appendix C of Cocoa Users' Manual by means of syntax graphs. Here we just give an informal description of this syntax.
- An expression consist of a list of terms separated by the (additive) operators: + , - .
- A term consists of factors separated by (multiplicative) operators, which are: * , : , mod , div , & .
- A factor consists of one of the followings
- a coefficient;
- an identifier (of an indeterminate or of an object);
- a function call
- an expression enclosed in round brackets
a factor can be possibly followed by an exponent and/or a substitution.
A coefficient is an integer (with or without sign ), eventually followed by the factorial operator ! , or a fraction i.e. a (signed) integer followed by the character ΓÇÿ/ΓÇÖ and a positive integer.
The multiplication symbol * can be omitted, and exponentiation does not require a symbol; it suffices to write the exponent with the appropriate characters .
The priority of the operations ΓÇô from the highest to the lowest ΓÇô is:
exponentiation, substitution
* , : , & , div, mod
+ , -
When in doubt, parentheses can be used to enforce a particular order of evaluation.
Operations with equal priority are performed from left to right.
The following table shows what operations the system can perform between two objects of the same or of different types; the first column contains is the type of the first operand and the first row the type of the second one.
